Let, y be a point in that intersection. Since, by definition, ˆr(x0,) is the radius of the smallest ball with 1/2 + probability mass of f(x0 + P) over all possible centers in Rk and ˆRis the radius of the smallest such ball centered at ˆf(x), we must have ˆr(x0,) ˆR. Consider the smallest ball B(z0,ˆr(x, 1)) that encloses at least 1/2 + 1 probability mass of f(x+ P). Since, r is the radius of the minimum enclosing ball that contains at least half of the points in Z, we have r ˆr(x, 1). Now, using the definition of ˆRand following the same reasoning as theorem 2, we can say that, d( ˆf(x), ˆf(x0)) βˆr(x0,) + ˆR (1 + β) ˆR.

The study of provable adversarial robustness has mostly been limited to classification tasks and models with one-dimensional real-valued outputs. We extend the scope of certifiable robustness to problems with more general and structured outputs like sets, images, language, etc. Such models are used in many machine learning problems like image segmentation, object detection, generative models, image/audio-to-text systems, etc. Based on a robustness technique called randomized smoothing, our center smoothing procedure can produce models with the guarantee that the change in the output, as measured by the distance metric, remains small for any norm-bounded adversarial perturbation of the input. We apply our method to create certifiably robust models with disparate output spaces -- from sets to images -- and show that it yields meaningful certificates without significantly degrading the performance of the base model.